第六讲 凹规划

Author

Affiliation

范翻

中央财经大学(CCFD)

凹函数及其导数 I

对于\(\theta \in [0,1]\)而言，称\(F(x)\)是凹函数，当且仅当:

\[ \begin{aligned} F(x^a + & \theta (x^b - x^a)) = F(\theta x^b + (1 - \theta) x^a) \geq \\ & \theta F(x^b) + (1 - \theta) F(x^a) \end{aligned} \]

稍作变形有 \[ \frac{F(x^a + \theta (x^b - x^a)) - F(x^a)}{\theta} \geq F(x) \]

当\(\theta \rightarrow 0\)，如果\(F\)是可微的，那么上式左边会趋近于\(F_x(x^a)(x^b - x^a)\)（洛必达法则）。因此有 \[ F_x(x^a) \geq \frac{F(x^b) - F(x^a)}{x^b - x^a} \]

凹函数及其导数 II

当\(x\)是一维的时候：

• \(F_x(x^a)\)就是函数\(F(x)\)在\(x^a\)处切线的斜率

• \(\frac{F(x^b) - F(x^a)}{x^b - x^a}\)是函数\(F(x)\)在点\(x^a, x^b\)之间连线的斜率

• 函数的凹性意味着切线位于函数曲线之上

凹规划（Concave Programming）的定义

凹规划是一类特殊的数学优化问题，其目标函数为凹函数，且约束条件定义的可行域为凸集。具体形式如下：

\[ \begin{aligned} \max_{x} \quad & f(x) \\ \text{s.t.} \quad & g_i(x) \geq 0, \quad i = 1, \dots, m, \\ & h_j(x) = 0, \quad j = 1, \dots, p, \\ & x \in X \subseteq \mathbb{R}^n, \end{aligned} \] 其中：

• 目标函数 \(f(x)\) 是凹函数（若为最小化问题，则要求 \(f(x)\) 是凸函数）。

• 不等式约束 \(g_i(x)\) 是凹函数（确保可行域 \(\{x \mid g_i(x) \geq 0\}\) 是凸集）。

• 等式约束 \(h_j(x)\) 是仿射函数（即线性函数加常数，形如 \(h_j(x) = a_j^T x + b_j\)）。

• 集合约束 \(X\) 是凸集（如 \(\mathbb{R}^n\) 或某个凸多面体）。

最大值函数的性质

对于每组给定的外生参数\(c\)，最优选择\(\bar{x}\)和最大值\(\bar{v} = F(\bar{x})\)都是\(c\)的函数。令\(X(c)\)表示最优选择函数，\(V(c)\)表示最大值函数：

• \(V\)对于\(c\)是非减函数，意味着约束条件放松，最大值不可能下降（最多持平）

• \(V\)是凹函数，换言之对于任意给定的两组投入要素\(c, c'\)，以及\(\theta \in [0,1]\)，最大值函数满足 \[ V(\theta c + (1 - \theta) c') \geq \theta V(c) + (1 - \theta) V(c') \]

凹性的证明 I

自然地，我们考虑\(\theta \bar{x} + (1 - \theta) \bar{x}'\)是否可以满足上述要求。

• 对于每一个\(j\)，约束条件\(G^j\)是凸的，意味着 \[ \begin{aligned} & G^{j}(\theta \bar{x} + (1 - \theta) \bar{x}') \\ & \leq \theta G^j(\bar{x}) + (1 - \theta)G^j(\bar{x}') \\ & \leq \theta c_i + (1 - \theta) c_i' \end{aligned} \]

• 因此，\(\theta \bar{x} + (1 - \theta) \bar{x}'\)是约束条件\(G(x) \leq \theta c_i + (1 - \theta) c_i'\)下的一个可行选择

凹性的证明 II

• 根据\(F\)的凹性有 \[ \begin{aligned} & F(\theta \bar{x} + (1 - \theta)\bar{x}') \\ & \geq \theta F(\bar{x}) + (1 - \theta) F(\bar{x}') \\ & \geq \theta \bar{v} + (1 - \theta) \bar{v}' \end{aligned} \]

• 而最大值\(V(\theta c + (1 - \theta) c')\)代表着所有可行选择中最大的收入，换言之，一定有 \[ \begin{aligned} & V(\theta c + (1 - \theta) c') \\ & \geq F(\theta \bar{x} + (1 - \theta)\bar{x}') \\ & \geq \theta \bar{v} + (1 - \theta) \bar{v}' \end{aligned} \]

经济学含义

• \(G\)为凸函数，排除了生产中的规模经济或专业化，确保了一个加权平均的产量能够通过相同权重的平均投入生产出来

• \(F\)为凹函数，保证了由此产生的收入大于等于各个收入的对应加权平均值

凹规划中的值函数

分离性质

• 集合A是所有满足\(v \leq V(c)\)的点\((c, v)\)的集合，意味着使用投入向量\(c\)进行生产，生产出的产品至少能带来\(v\)的收入

• 在集合A中选择一点\((c^*, v^*)\)，使得\(v^* = V(c^*)\)，这必然是一个边界点

• 集合B是所有满足\(c \leq c^*\)和\(v \geq v^*\)的点\((c, v)\)的集合

分离超平面： \[ \epsilon v - \lambda c = b = \epsilon v^* - \lambda c^* \] 其中\(\epsilon\)是一个标量，\(\lambda\)是一个m维向量，且满足 \[ \epsilon v - \lambda c \begin{cases} \leq b, & \forall (c,v) \in A \\ \geq b, & \forall (c,v) \in B \end{cases} \]

约束规格

斯拉特条件

斯拉特条件：集合A至少存在一个内点\(x_0\)使得\(G(x_0) \ll c^*\)，即\(x_0\)满足所有约束条件且严格不等式成立

证明思路：

• 假设存在\(x_0\)满足所有约束严格不等式 - 当\(\epsilon = 0\)时推导矛盾

• 得出结论\(\epsilon > 0\)

关键等式： \[ \lambda(G(x_0) - c^*) = \sum_{i=1}^m \lambda_i(G^i(x_0) - c_i^*) < 0 \]

影子价格

• 令\(\epsilon = 1\)，则\(\lambda\)解释为投入要素的影子价格

• 最大值函数\(V\)的可微性导致\(\lambda = V_c(c^*)\)

• 当\(V\)不可微时，存在双边不等式： \[ V_i^- \geq \lambda_i \geq V_i^+ \]

一般化的边际产品

选择变量

通过分离定理推导关键不等式： \[ F(\bar{x}) - \lambda G(\bar{x}) \leq V(c) - \lambda c \]

结合互补松弛条件：

• 对于每个约束\(i\)，\(\lambda_i[c_i - G^i(\bar{x})] = 0\)

• 要么\(\lambda_i = 0\)，要么\(G^i(\bar{x}) = c_i\)

凹规划的必要条件

若\(\bar{x}\)是凹规划问题的最优解，存在向量\(\lambda\)满足：

• \(\bar{x}\)在无约束下最大化\(F(x) - \lambda G(x)\)

• \(\lambda \geq 0\)且满足互补松弛条件

• 可微情形下的一阶条件： \[ F_{x}(\bar{x}) - \lambda G_{x}(\bar{x}) = 0 \]

凸规划的充分条件 I

若\(\bar{x}\)满足：

• 最大化\(F(x) - \lambda G(x)\)

• 满足互补松弛条件

则对任意可行\(x\)有： \[ F(\bar{x}) \geq F(x) \]

利用凹函数性质： \[ [F(x) - \lambda G(x)] - [F(\bar{x}) - \lambda G(\bar{x})] \leq 0 \]

凹规划的充分条件 II

若\(\bar{x}\)和\(\lambda\)满足以下条件：

• \(\bar{x}\)在无约束的情况下最大化了\(F(x) - \lambda G(x)\)

• \(\lambda \geq 0\)和\(G(\bar{x}) \leq c\)满足互补松弛条件

那么\(\bar{x}\)在约束\(G(x) \geq c\)下最大化\(F(x)\)。如果\((F - \lambda G)\)是凹函数，那么 \[ F(x) - \lambda G(x) \leq F(\bar{x}) -\lambda G(\bar{x}) \] 也意味着条件(i)成立。

拟凹规划 (\(F\)拟凹，\(G\)为线性函数)

如果\(F\)为拟凹函数，那么 \[ \begin{aligned} F((1 - \theta) x^a + \theta x^b) \geq \min(F(x^a), F(x^b)) \end{aligned} \]

假定\(F(x^b) \geq F(x^a)\)，那么 \[ F(x^a + \theta(x^b - x^a)) \geq F(x^a) \]

将上式看作关于\(\theta\)的函数： \[ h(\theta) \geq h(0), \quad \forall \theta \in [0,1] \]

通过链式法则推导： \[ \begin{aligned} h'(\theta) &= F_x(x^a + \theta (x^b - x^a))(x^b - x^a) \\ h'(0) &= F_x(x^a)(x^b - x^a) \geq 0 \end{aligned} \]

拟凹规划 II

考虑在线性约束\(px \leq b\)下最大化\(F(x)\)，最优解必要条件为： \[ F_x(\bar{x}) - \lambda p = 0 \]

充分性证明： 对任意满足\(F(x) > F(\bar{x}) \equiv \bar{v}\)的\(x\)，取\(x^a = \bar{x}\)和\(x^b = x\)，由拟凹性可得： \[ F_x(\bar{x})(x - \bar{x}) \geq 0 \]

拟凹规划 III

结合必要条件推导： \[ p(x - \bar{x}) \geq 0 \Rightarrow px \geq p\bar{x} \]

反证结论：

• 若\(px = p\bar{x}\)，则\(x\)在满足约束下得到更大\(F\)，矛盾

• 故必有\(px > p\bar{x}\)，即\(x\)不可行